COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00010 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a113.tex[106,phy] \today\hfill}

%\def\ninepoint{\def\rm{\fam0\ninerm}%
%  \def\sl{\fam\slfam\ninesl}
%  \textfont\slfam=\ninesl
%  \rm}
\font\rmn=cmr9
\line{\bf Case Study: The Back of the Envelope\hfill}

$$\vcenter{\halign{$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad\quad
&$\hfil#\hfil$\qquad\quad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\cr
&&&&&&&&&f(x)\cr
\noalign{\bigskip\bigskip\bigskip\bigskip}
&&&&&\bullet\cr
\noalign{\bigskip}
&&&\bullet\cr
\noalign{\bigskip}
&\bullet\cr
\noalign{\bigskip\bigskip}
0&&{1\over N}&&{2\over N}&&{3\over N}&\ldots&1&x\cr}}$$

I want to estimate $\int↓0↑1f(x)\,dx$ numerically by a sum of rectangular
areas, as shown. The area of the rectangle of width $1/N$ and height
$f\bigl({i+{1\over 2}\over N}\bigr)$ approximates $\int↓{i/N}↑{(i+1)/N}
f(x)\,dx$. The method has two sources of error:

\smallskip
\disleft 20pt:$\bullet$:
The area of the rectangle is not the same as the integral.

\smallskip
\disleft 20pt:$\bullet$:
Rounding error enters the computation at every step.

\smallskip\noindent
If $N$ is very small, the error of approximation is obviously very large.
Less obviously, if $N$ is very large, the computed sum is not even a very
accurate sum of the rectangular areas. I~can't know exactly the right choice
of~$N$ without knowing in advance the exact integral. I~can make a reasonable
decision based on rough estimates. These estimates are typically made by
hand, and require only one or two digits of precision; they are therefore
called {\sl back-of-the-envelope\/} calculations.

The first source of error decreases as $N$ increases; the second increases.
I~can therefore {\sl trade off\/} error of one kind for the other by making
$N$ larger or smaller. If I~knew exact formulas for the errors, I~could
use methods of the calculus to minimize the sum. Since I~will only have 
estimates, I~can do well enough by choosing~$N$ to make the two sources
of error about equal. That way, I~know that no other choice of~$N$ can
cut the error by more than a (wildly optimistic) factor of two.

$$\vcenter{\halign{$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\cr
\noalign{\bigskip\bigskip\bigskip}
&\bullet\cr
\noalign{\bigskip}
&\bullet\cr
\noalign{\smallskip}
{i\over N}&{i+{1\over 2}\over N}&{i+1\over N}\cr}}$$

Let's suppose $f(x)$ is something like $x↑2$. At a typical point about
halfway through the computation, a step like
$$S:=S+f\left.\bigl((i+0.5)/N\bigr)\right/N$$
adds the estimated area shown. The error added to~$S$ in the process is
about
$$\int↓{i/N}↑{(i+1)/N}x↑2\,dx-{{(i+0.5)↑2\over N}\over N}=
{3i↑2+3i+1\over 3N↑3}-{i↑2+i+0.25\over N↑3}={1\over 12N↑3}$$
from the rectangular approximation, and about $\epsilon↓MS$ from the
rounding. $S$~is around $1/6$ on the average, and if $\epsilon↓M$ is
around $10↑{-8}$, we want 
${1\over 12N↑3}={10↑{-8}\over 6}$,
$N=\root 3\of{10↑8\over 2}$, around 400.
At that point, the total error is about
$N\bigl({1\over 12N↑3}+\epsilon↓MS\bigr)$, or
$5\times 10↑{-7}+8\times 10↑{-7}$, for a total of about $10↑{-6}$. A~more
refined estimate would not change either the choice of~$N$ or the estimated
error by more than a factor of two.

In computer programming, as in every branch of engineering, the best is
seldom achievable, but good enough is very important. The 
back-of-the-envelope computation addresses the practical quantitative questions:

\smallskip
\disleft 20pt:$\bullet$:
Will the program run fast enough?

\smallskip
\disleft 20pt:$\bullet$:
Will it fit in the computer memory?

\smallskip
\disleft 20pt:$\bullet$:
Will the results be accurate enough?

\smallskip
\disleft 20pt:$\bullet$:
Will the total cost of programming, debugging, and execution be reasonable?

\smallskip\noindent
It is part of the professonalism of computer programming to answer these
questions.

\disleft 38pt::
{\rmn
{\bf Drill.} The estimate given neglects the likelihood, on rounding
machines, that rounding errors will tend to cancel. Redo the back-of-the-envelope
calculation for a rounding machine.
}

\bigskip
\line{\copyright 1986 Robert W. Floyd; 
First draft (not published) October 6, 1986\hfil}
%revised: Date; subsequently revised.\hfill}

\bye